package leetcode_core.leetcode_1;

import org.junit.Test;

public class Change {

    public int change(int amount, int[] coins) {
        //1.定义dp数组,dp[i][j]:表示的是选择前i个物品,在j的背包容量下,共有几种凑法
        int[][] dp = new int[coins.length+1][amount+1];
        //2.定义base-case
        //当i=0的时候,表示没有硬币可以选
        //当j=0的时候,表示背包没有容量,如果背包没有容量,那么这也是一种凑法,因为根据定义来说,我们都根本不用选硬币
        dp[0][0]=0;
        for(int i = 0;i<=coins.length;i++){
            dp[i][0] = 1;
        }
        for(int j = 0;j<=amount;j++){
            dp[0][j] = 0;
        }
        //3.开始状态转移计算,由base-case得到的DP-table可知从(1,1)开始
        for(int i = 1;i<=coins.length;i++){
            for(int j = 1;j<= amount; j++){
                //如果当前的背包容量装不下,那么只能够不选
                if(j-coins[i-1] <0 ){
                    dp[i][j] = dp[i-1][j];
                }else{
                    //如果装得下,那么我们把两种凑法都纳入进来
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                }
            }
        }
        return dp[coins.length][amount];
    }

    @Test
    public void testCaseOne(){
        System.out.println(change(5, new int[]{1, 2, 5}));
    }
    @Test
    public void testCaseTwo(){
        System.out.println(change(5, new int[]{2}));
    }
}
